// 丑数2

package Leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

class Solution_264_1 {
    public int nthUglyNumber(int n) {
        int start = 1;
        int count = 0;
        while (count != n) {
            if (isUgly(start))
                count++;
            start++;
        }
        return --start;
    }

    public boolean isUgly(int n) {
        if (n <= 0) {
            return false;
        }
        int[] factors = { 2, 3, 5 };
        for (int factor : factors) {
            while (n % factor == 0) {
                n /= factor;
            }
        }
        return n == 1;
    }
}

class Solution_264_2 {
    public int nthUglyNumber(int n) {
        List<Integer> uglyNum = new ArrayList<>();
        for (int i = 0;; i++) {
            for (int j = 0; j <= i; j++) {
                for (int k = 0; k <= i - j; k++) {
                    uglyNum.add((int) Math.pow(5, j) * (int) Math.pow(3, k) * (int) Math.pow(2, i - j - k));
                }
            }
            if (uglyNum.size() == n + 10)
                break;
        }
        Collections.sort(uglyNum);
        uglyNum.forEach(i -> System.out.println(i));
        return uglyNum.get(n - 1);
    }
}

class Solution_264_3 {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int a = 1, b = 1, c = 1;
        for (int i = 2; i <= n; i++) {
            int num1 = dp[a] * 2;
            int num2 = dp[b] * 3;
            int num3 = dp[c] * 5;
            dp[i] = Math.min(num1, Math.min(num2, num3));
            if (dp[i] == num1)
                a++;
            if (dp[i] == num2)
                b++;
            if (dp[i] == num3)
                c++;
        }
        return dp[n];
    }
}

class Solution_264_4 {
    public int nthUglyNumber(int n) {
        int[] factors = new int[] { 2, 3, 5 };
        Set<Long> set = new HashSet<>();
        PriorityQueue<Long> heap = new PriorityQueue<>();
        // 将初始的丑数 1 加入 set 和 heap
        set.add(1L);
        heap.add(1L);
        int uglyNum = 0;
        for (int i = 0; i < n; i++) {
            long currentMin = heap.poll();
            uglyNum = (int) currentMin;
            for (int factor : factors) {
                Long nextUgly = factor * currentMin;
                // 判断是否存在于 set，防止重复
                if (!set.contains(nextUgly)) {
                    set.add(nextUgly);
                    heap.add(nextUgly);
                }
            }
        }
        return uglyNum;
    }
}